/**
 * @link https://leetcode.cn/problems/is-subsequence/?envType=study-plan-v2&envId=top-interview-150
 */
function isSubsequence(s: string, t: string): boolean {
  let p1 = 0;
  let p2 = 0;
  if (s === "") return true;
  while (p1 < s.length && p2 < t.length) {
    if (s[p1] === t[p2]) {
      p1 += 1;
    }
    p2 += 1;
    if (p1 === s.length) {
      return true;
    }
  }

  return false;
}

/**
 * @link https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/?envType=study-plan-v2&envId=top-interview-150
 */
function twoSum(numbers: number[], target: number): number[] {
  let start = 0;
  let end = numbers.length - 1;
  while (start < end) {
    if (numbers[start] + numbers[end] === target) {
      return [start + 1, end + 1];
    }
    if (numbers[start] + numbers[end] > target) {
      end -= 1;
    } else {
      start += 1;
    }
  }
  return [];
}

/**
 * @link https://leetcode.cn/problems/container-with-most-water/?envType=study-plan-v2&envId=top-interview-150
 */
function maxArea(height: number[]): number {
  let start = 0;
  let end = height.length - 1;
  let h = Math.min(height[start], height[end]);
  let ans = (end - start) * h;
  while (start < end) {
    h = Math.min(height[start], height[end]);
    ans = Math.max((end - start) * h, ans);
    if (height[start] <= height[end]) {
      while (start + 1 < height.length && height[start + 1] < h) {
        start += 1;
      }
      start += 1;
    } else {
      while (end - 1 >= 0 && height[end - 1] < h) {
        end -= 1;
      }
      end -= 1;
    }
  }
  return ans;
}

/**
 * @link https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=top-interview-150
 */
function threeSum(nums: number[]): number[][] {
  nums = nums.sort((a, b) => a - b);
  console.log(nums);
  let ans = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i >= 1 && nums[i] === nums[i - 1]) {
      continue;
    }
    let lp = i + 1;
    let rp = nums.length - 1;
    while (lp < rp) {
      if (nums[i] + nums[lp] + nums[rp] === 0) {
        console.log(i, lp, rp);
        ans.push([nums[i], nums[lp], nums[rp]]);
        while (nums[lp + 1] === nums[lp]) lp += 1;
        while (nums[rp - 1] === nums[rp]) rp -= 1;
        lp += 1;
        rp -= 1;
      } else if (nums[i] + nums[lp] + nums[rp] > 0) {
        rp -= 1;
      } else {
        lp += 1;
      }
    }
  }
  console.log(ans);

  return ans;
}

export default { isSubsequence, twoSum, maxArea, threeSum };
